package com.hanlin.leetcode;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 队列实现栈
 * https://leetcode.cn/problems/implement-stack-using-queues/
 */
public class QueueToStack {

    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        System.out.println(myStack.top());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.empty());
    }

}

class MyStack {


    private Queue<Integer> queue = null;
    private Queue<Integer> helper = null;

    public MyStack() {
        queue = new LinkedList<>();
        helper = new LinkedList<>();
    }

    /**
     * 将元素 x 压入栈顶
     *
     * @param x
     */
    public void push(int x) {
        queue.offer(x);
    }

    /**
     * 移除并返回栈顶元素
     *
     * @return
     */
    public int pop() {
        if (empty()) {
            throw new RuntimeException("栈是空的");
        }
        while (queue.size() > 1) {
            helper.offer(queue.poll());
        }
        Integer pop = queue.poll();
        Queue<Integer> tmp = queue;
        queue = helper;
        helper = tmp;
        return pop;
    }

    /**
     * 返回栈顶元素
     *
     * @return
     */
    public int top() {
        if (empty()) {
            throw new RuntimeException("栈是空的");
        }
        while (queue.size() > 1) {
            helper.offer(queue.poll());
        }
        Integer pop = queue.poll();
        helper.offer(pop);
        Queue<Integer> tmp = queue;
        queue = helper;
        helper = tmp;
        return pop;
    }

    /**
     * 如果栈是空的，返回 true ；否则，返回 false
     *
     * @return
     */
    public boolean empty() {
        return queue == null || queue.isEmpty();
    }
}